//
// Description: 547. 省份数量
// Created by Loading on 2021/7/30.
//

/* 典型的并查集算法 */

#include <bits/stdc++.h>

using namespace std;

const int N = 201; // 数据量
int father[N];     // 集 （父节点集合）

// 初始化
void Init(int n) {
    // 在合并之前初始化每个节点为该集合的根节点（每个数都是一个集合，自己的父节点初始化为自己）
    for (int i = 1; i <= n; i++) {
        father[i] = i;
    }
}

// 查
int FindFather(int x) {
    /* 功能：找到元素x在该集合中的根节点（根节点满足x == father[x]） */

    // 记录初始节点
    int a = x;
    // 循环查找父节点，找到集合的根节点
    while (x != father[x]) {
        x = father[x];   // 循环结束后的 x 为该集合的根节点
    }
    /* 路径压缩，将寻找根节点路途中的每个节点指向其根节点，优化之后的查找速度，可不写 */
    while (a != father[a]) {
        int b = a;      // 记录 a，防止后面被覆盖
        a = father[a];  // 让 a 指向其父节点
        father[b] = x;  // 指向根节点
    }
    return x;
}

// 并
void Union(int a, int b) {
    /* 功能：将 a 与 b 合并到一个集合中 */

    // 分别找到 a, b 所在结合的根节点
    int Ra = FindFather(a);
    int Rb = FindFather(b);
    // 当 a, b 不在同一个集合中时将 Ra 指向 Rb，或者将 Rb 指向 Ra （选择一个作为根节点）
    if (Ra != Rb) {
        // 将 Ra 指向 Rb
        father[Ra] = Rb;
        // father[Rb] = Ra; 也可以
    }
}

int findCircleNum(vector<vector<int>> &isConnected) {
    int n = isConnected.size();
    Init(n);
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (isConnected[i][j] == 1) {
                Union(i + 1, j + 1);
            }
        }
    }

    int provinces = 0;
    for (int i = 1; i <= n; ++i) {
        /* 父节点仍是自己，表示是一个省份的根节点 */
        if (father[i] == i) {
            ++provinces;
        }
    }

    return provinces;
}

int main() {
    vector<vector<int>> isConnected = {{1, 0, 0, 1},
                                       {0, 1, 1, 0},
                                       {0, 1, 1, 1},
                                       {1, 0, 1, 1}};

    cout << findCircleNum(isConnected) << endl;
}